The present invention concerns an anti-SPA (“Simple Power Attack”) modular exponentiation algorithm in an electronic component using a public key ciphering algorithm.
The characteristics of public key cryptography algorithms are known: calculations made, parameters used. The only unknown is the private key contained in the program memory of an electronic component, such as a smart card. The entire security of these cryptography algorithms resides in this private key contained in the card and unknown to the world outside this card. This private key cannot be deduced solely from knowledge of the message applied as an input and the encoded message supplied in return or from knowledge of the public key.
However, it has become clear that external attacks, based on the current consumptions or an analysis of current consumption when the microprocessor in a card is in the process of running the cryptography algorithm for signing a message or deciphering a message, enable ill-intentioned third parties to find the private key contained in this card. These attacks are referred to as SPA attacks, the English acronym for Single Power Analysis.
The principle of these SPA attacks is based on the fact that the current consumption of the microprocessor executing the instructions varies according to the data manipulated.
In particular, when an instruction executed by the microprocessor requires manipulation of a data item bit by bit, there are two different current profiles depending on whether this bit is “1” or “0”. Typically, if the microprocessor manipulates a “0”, there is at this moment of execution a first consumed current amplitude and if the microprocessor manipulates a “1” there is a second consumed current amplitude different from the first.
Thus the SPA attack exploits the difference in the current consumption profile in the card during the execution of an instruction according to the value of the bit manipulated. In a simplified manner, the conduct of an SPA attack consists of identifying one or more particular periods during which the algorithm is run comprising the execution of at least one instruction manipulating data bit by bit and distinguishing two different current consumption profiles, one corresponding to the manipulation of a bit equal to “0” and the other corresponding to a bit equal to “1”. The analysis takes place over a curve or possibly over n curves of the same running of the algorithm averaged in order to eliminate noise.
Modular exponentiation is defined by the following mathematical formula:R=XY mod N,
in which:
Y is an exponent which has a size of k bits;
N is a modulus which has a size of k′ bits;
X is a known variable which has a size of k″ bits;
R is the result of the modular exponentiation operation and has a size of k′ bits.
The known conventional algorithms A or B described below can be used.
The conventional algorithm A used for calculating the above mentioned mathematical formula is as follows:                R is initialised to 1: R=1;        The binary representation of Y is run through from the most significant bit denoted Y(k−1) to the least significant bit Y(0);        for each bit Y(i), i varying from (k−1) to 0, the additional operation R=R2 is performed.        
If the bit Y(i) is equal to 1, an additional step is executed which consists of the operation:R=R*X.
If for example Y is equal to 5, its binary representation is 101;
If the above algorithm is applied:                for the first bit [Y(2)=1], R=R2 is effected followed by the operation R=R*X, that is to say the result, R=X;        for the second bit [Y(1)=0], the operation R=R2 is performed, that is to say the result, R=X2;        for the third bit [Y(0)=1], the operation R=R2 is performed, followed by the operation R=R*X, that is to say the result, R=(X2)2*X=X5.        
As a reminder, the previous R is always used.
Naturally, all the mathematical operations described for the example Y is equal to 5 are performed modulo N, which makes it possible to work with a register r with a size of k′ bits.
The conventional algorithm B used for calculating the abovementioned mathematical formula is as follows:                R is initialised to 1 and Z to X:                    R=1 and Z=X, Z being a variable:                        the binary representation of Y is run through from the least significant bit Y(0) to the most significant bit Y(k−1);        
for each bit Y(i), i varying from 0 to (k−1), the additional operation Z=Z2 is performed, when i is greater than 0;
if the bit Y(i) is equal to 1, an additional step is executed which consists of the operation:R=R*Z.
If for example Y is equal to 5, its binary representation is 101.
If the above algorithm is applied:                for the first bit, Y(0)=1; the operation Z=Z2 is not performed (since i=0) and the operation R=R*Z=X is performed;        for the second bit [Y(1)]=0, the operation Z=Z2=X2 is performed; R is unchanged since Y(1)=0;        for the third bit [Y(2)=1], the operation Z=Z2=X4 is performed and as Y(2) is equal to 1 the operation R=R*Z is also performed and therefore X5 is obtained.        
As a reminder, the previous R and Z are always used.
Naturally, all the mathematical operations described for the example Y is equal to 5 are performed modulo N, which makes it possible to work with registers r and z with a size of k′ bits.
However, this algorithm B is rarely used in an electronic component of the chip card type since it requires more memory (an additional register z with a size of k′ bits).
It is found that, on the conventional algorithms A and B explained above, according to each bit of Y one operation is performed if the bit is 0 and two operations if the bit is 1. These algorithms A and B are used for the RSA. As a reminder, the RSA ciphering system is the most widely used public key ciphering system. It can be used as an ciphering method or as a signature method. The RSA ciphering system is used in chip cards for certain applications thereof. The possible applications of RSA on a chip card are access to data banks, banking applications, distance payment applications, such as for example pay television, petrol dispensing or the payment of motorway tolls. This list of applications is of course not exhaustive.
The principle of the RSA ciphering system is as follows. It can be divided into three distinct parts, namely:
1) The generation of the pair of RSA keys;
2) The ciphering of a message in clear into a ciphered message, and
3) The deciphering of a ciphered message into a message in clear.
The RSA ciphering operation consists of calculating a cipher c which is equal to a message Me mod N represented by the operation C=Me mod N, in which e is the public ciphering exponent and N is the modulus.
An RSA deciphering operation consists of calculating a message M′ which is equal to M if the deciphering is carried out correctly and is represented by the operation:M′=Cd mod N,
in which d is the private deciphering exponent and N the modulus.
It is found that the RSA is directly a modular exponentiation operation.
It turns out that d is an element which is secret since it is private; it is therefore found that d is equivalent to Y in the conventional algorithm A or B, algorithms described at the beginning of the description. However, these algorithms used for the RSA can be attacked simply by studying the current consumption of the electronic component implementing the invention.
This is because, if it is considered that the signature S of an operation R2 for algorithm A and Z2 for algorithm B referred to as “operation square”, denoted S(SQU), is different from the signature S of the operation R*X for algorithm A and Z*R for algorithm B, referred to as “operation multiply”, denoted S(MUL), then the current consumption during the execution of the algorithm A or B described above consists of a series of signatures S(SQU) and S(MUL) directly dependent on Y.
For example, in the case of algorithm A, for Y equal to 5, there will be the following series of signatures:
[S(SQU), S(MUL)], [S(SQU)], [S(SQU), S(MUL)], in which series the signatures [S(SQU)] followed by [S(MUL)] corresponds to a bit equal to 1 and the signature [S(SQU)] followed by the signature [S(SQU)] corresponds to a bit equal to 0.
Simply by looking at the current consumption, if it is known how to differentiate S(SQU) from S(MUL), it is possible to find the whole of the value Y. If this attack is applied to the RSA described above, Y=d is found, which is the private deciphering exponent which must remain secret by definition, which is therefore very awkward.
The present invention makes it possible to eliminate this major drawback.
However, in order to clearly emphasise the inventiveness of the present invention, it is useful to describe an example of an improvement to the algorithms A and B which are nevertheless faulty.
In the conventional algorithm A or B, it is considered that the component which implements the invention has an optimised operation referred to as “Square”, denoted SQU, which calculates R2 more effectively than the operation “Multiply”, denoted MUL.
The first riposte against attack consists of using only the operation MUL. In this case, there remains nothing more than the signature of the operation “Multiply”, which no longer makes it possible to distinguish any information making it possible to go back to the value Y. More precisely, the mathematical operation “Multiply” has two operands V and W and is defined by the formula:MUL(V,W)=V*W.
In theory, one is protected but in practice the operation MUL(V,V) or the operation MUL(V,W) is used; there is therefore still a difference in the current consumption since the operands are different. This is not a reliable solution.